// https://leetcode.cn/problems/delete-and-earn/

// 题干：给你一个整数数组 nums ，你可以对它进行一些操作。
//      每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
//      之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
//      开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

// 示例：输入：nums = [3,4,2]
//      输出：6

// 碎语：化未知为已知，这是一个很重要的能力，尝试能不能联系上打家劫舍

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int deleteAndEarn(vector<int>& nums)
    {
        const int N = 10001;
        // 无下标，排序后无影响
        // 不能选择相邻的两个数，如果靠近的话
        // 并且能很自然的想到哈希表

        // 先做以下预处理，将数组的数统计到arr中，然后在arr中做一次打家劫舍
        // 状态转移方程，选到i位置的时候，nums[i]必选，此时能获得的最大点数
        //  选到i位置的时候，nums[i]不选，此时能获得的最大点数

        // 1.预处理
        int arr[N] = {0};
        for (const auto& num : nums) arr[num] += num;

        // 2.在arr数组的基础上做一次打家劫舍
        vector<int> f(N), g(N);
        for (int i = 1 ; i < N ; i++){
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[N - 1], g[N - 1]);
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {3,4,2};

    cout << sol.deleteAndEarn(nums) << endl;

    return 0;
}

